package com.zp.self.module.level_4_算法练习.算法.动态规划;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_72_编辑距离 {
    //测试
    public static void main(String[] args) {

//        System.out.println(new 力扣_72_编辑距离().minDistance("horse","ros"));
//        System.out.println(new 力扣_72_编辑距离().minDistance("ab","ccccccab"));
//        System.out.println(new 力扣_72_编辑距离().minDistance("intwqeqwwq" ,"execwqu"));
        System.out.println(new 力扣_72_编辑距离().minDistance("aaaaaxa" ,"bxbbbbb"));
    }

    /**
    题目：给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
     你可以对一个单词进行如下三种操作：
     插入一个字符
     删除一个字符
     替换一个字符

     示例 1：
     输入：word1 = "horse", word2 = "ros"
     输出：3
     解释：
     horse -> rorse (将 'h' 替换为 'r')
     rorse -> rose (删除 'r')
     rose -> ros (删除 'e')

     示例 2：
     输入：word1 = "intention", word2 = "execution"
     输出：5
     解释：
     intention -> inention (删除 't')
     inention -> enention (将 'i' 替换为 'e')
     enention -> exention (将 'n' 替换为 'x')
     exention -> exection (将 'n' 替换为 'c')
     exection -> execution (插入 'u')

    分析：【BR 💘💘💘💘💘💘】
       1.动态规划--二维：
         一、如果我们 word1[i] 与 word2 [j] 相等，这个时候不需要进行任何操作，显然有 dp[i] [j] = dp[i-1] [j-1]。（别忘了 dp[i] [j] 的含义哈）。
         二、如果我们 word1[i] 与 word2 [j] 不相等，这个时候我们就必须进行调整，而调整的操作有 3 种，我们要选择一种。三种操作对应的关系试如下（注意字符串与字符的区别）：
         （1）、如果把字符 word1[i] 替换成与 word2[j] 相等，则有 dp[i] [j] = dp[i-1] [j-1] + 1;
         （2）、如果在字符串 word1末尾插入一个与 word2[j] 相等的字符，则有 dp[i] [j] = dp[i] [j-1] + 1;
         （3）、如果把字符 word1[i] 删除，则有 dp[i] [j] = dp[i-1] [j] + 1;
            状态方程： char1[x]==char2[y]  ？ dp[x+1][y+1] = dp[x][y]  ： dp[x+1][y+1] = Math.min(dp[x][y],Math.min(dp[x+1][y],dp[x][y+1]))+1;

    边界值 & 注意点：
       1.
     **/
    public int minDistance(String word1, String word2) {
        char[] char1=word1.toCharArray();
        char[] char2=word2.toCharArray();
        int row =word1.length(),lie =word2.length();
        int[][] dp = new int[row+1][lie+1];
        for (int i = 1; i <= row; i++)   dp[i][0] =i;//初始化第一列
        for (int i = 1; i <= lie; i++)   dp[0][i] =i;//初始化第一行
        for (int x = 0; x < row; x++) {
            for (int y = 0; y < lie; y++) {
                if(char1[x]==char2[y]) dp[x+1][y+1] = dp[x][y];
                else dp[x+1][y+1] = Math.min(dp[x][y],Math.min(dp[x+1][y],dp[x][y+1]))+1;
            }
        }
        return dp[row][lie];
    }
}

